This invention relates, in its most general aspects, to a computer system and to a method of operating that system, and to improvements in the performance of various operations within such a system. It also relates to a computer-readable storage medium. The computer system may be, may include, or may be part of, a virtual machine. The computer-readable storage medium may contain executable code or other instructions for programming the computer system/virtual machine.
In recent years, there have been developments in programming languages towards what is known as an object-oriented language. In these developments, concepts are regarded as xe2x80x98objectsxe2x80x99, each carrying with it a set of data, or attributes, pertinent to that object, as well as information relating to so-called xe2x80x98methodsxe2x80x99, that is functions or sub-routines, that can be performed on that object and its data. This is well known to those skilled in the art of computing and/or programming.
The advent and rapid advancement in the spread and availability of computers has led to the independent development of different types of systems, such as the IBM and IBM-compatible PC running IBM-DOS or MS-DOS or MS-Windows applications, the Apple Macintosh machines running their own Apple System operating system, or various Unix machines running their own Unix operating systems. This proliferation of independent systems has led to useful applications being available only in one format and not being capable of running on a machine for which the application was not designed.
Under such circumstances, programmers have devised -software which xe2x80x98emulatesxe2x80x99 the host computer""s operating system so that a xe2x80x98foreignxe2x80x99 application can be made to run successfully in such a way that, as far as the user is concerned, the emulation is invisible. In other words, the user can perform all of the normal functions of say a Windows-based application on a Unix machine using a Unix-based operating system without noticing that he is doing so.
A particularly notable product of this type is that developed by Insignia Solutions of High Wycombe, GB and Santa Clara, Calif., USA and known under the name xe2x80x98SoftWindows 2.0 for Powermacxe2x80x99. This software enables a physical Macintosh computer to emulate a PC having an Intel 80486DX processor and 80487 maths co-processor plus memory, two hard disks, IBM-style keyboard, colour display and other features normally found on recent versions of the PC-type of computer.
Furthermore, there is an ever-increasing demand by the consumer for electronics gadgetry, communications and control systems which, like computers, have developed independently of one another and have led to incompatibility between operating systems and protocols. For example, remote-control devices for video players, tape players and CD players have similar functions, analogous to xe2x80x98play,xe2x80x99 xe2x80x98forward,xe2x80x99 xe2x80x98reverse,xe2x80x99 xe2x80x98pause,xe2x80x99 etc, but the codes for transmission between the remote control, or commander, operated by the user may not be compatible either between different types of equipment made by the same manufacturer or between the same types of equipment made by different manufacturers. There would be clear benefits of having software within the equipment which can produce for example the correct xe2x80x98playxe2x80x99 code based upon a xe2x80x98playxe2x80x99 command regardless of the specific hardware used in the equipment. Such software is commonly known as a xe2x80x98Virtual Machine.xe2x80x99
Other uses and applications are legion: for example, set-top boxes for decoding television transmissions, remote diagnostic equipment, in-car navigation systems and so-called xe2x80x98Personal Digital Assistants.xe2x80x99 Mobile telephones, for instance, can have a system upgrade downloaded to them from any service provider.
Emulation software packages tend to have certain features in common, notably that they are not general purpose but are dedicated. They are of most benefit in rapid development areas and have a distinct advantage in enabling manufacturers to cut costs. In particular, they can divorce software from the physical machine, i.e., the effect of the software in the physical machine can be altered by the emulating software without having to go into the machine""s native software to implement those changes.
The specific object-oriented language used in some of the implementations described later is that known as Java (registered trade mark to Sun Microsystems Corporation). Some of the following implementations will enable Java to be used in smaller devices than is currently possible because of the improved performance and/or reduced memory footprint. Future uses projected for embedded software (virtual machines) include computers worn on the body, office equipment, household appliances, and intelligent houses and cars.
While it is recognised that there are clear advantages in the use of virtual machines, especially those using object-oriented languages, there are naturally areas where it is important and/or beneficial for some of the operations that are carried out within the system to be optimised. These may include reducing the memory requirement, increasing the speed of operation, and improving the xe2x80x98transparencyxe2x80x99 of the system when embedded in another system. One of the principal aims of the inventions described herein is to provide a Virtual Machine which is optimised to work as quickly as possible within a memory constraint of, for example, less than 10, 5, 2 or even 1 Mbyte. Such a constraint is likely to be applicable, for example, to electronics gadgetry and other equipment where cost (or size) is a major constraint.
The invention relates to a method of and apparatus for examining memory in a computer system to allow a section of compiled code to be deleted, and to a method of and apparatus for deleting compiled code in a computer system. The invention finds particular (but not exclusive) application in the environment of a unified stack virtual machine in which stack walking allows compiled code to be deleted. In a preferred embodiment, the invention relates to stack walking to allow compiled code deletion in the multi-threaded environment of a unified stack virtual machine
The invention applies preferably to virtual machines where compiled portions of the code being run in the virtual machine appear and need to be removed at various times in the execution of the virtual machine; for example, in a dynamically compiling virtual machine.
When executing code using a virtual machine, we have found that it is advantageous to produce a compiled version of some or all of the emulated code (see Agent""s Reference No. 1 in this specification). We believe that it will sometimes be desirable or necessary to subsequently remove some or all of these compiled versions. Also we believe that it would be advantageous to use a single stack to support the stack requirements of both the emulated machine and also the needs of the virtual machine code itself, and to use a native call instruction to perform the equivalent of an emulated call (invoke) and use of a native return instruction to perform the equivalent of an emulated return in the code being run on the virtual machine.
Where a computer system has finished using memory which it has taken to perform a particular function we have found that it is in the interests of speed and efficiency that the used memory is returned as soon as possible for further use.
Currently known techniques for virtual machines would require that one or more of the optimising techniques listed in the background information section be not taken advantage of, or require explicit checks to be used which impair the efficiency of the system.
In particular, the deletion of compiled code from a system can give rise to problems. There may be a link from a section of compiled code which is not being deleted into a section of deleted code. Particular problems can arise because of the proposed use of a native call instruction (or equivalent) to emulate a call or invoke in the virtual machine; this would typically leave the address where execution is to continue once the called method is complete (thexe2x80x9creturn addressxe2x80x9d) on that stack for that thread, at or near the stack point when the call or invoke is performed. If the native call instruction is part of a compiled version of a section of code, then the return address will point into the compiled version. This causes no problems until the point of deletion of the compiled version. The return address cannot be left pointing to where the compiled version used to be. If, during execution, a thread tried to return to the address where the compiled code used to be, an error would occur and execution by that thread would usually terminate. In such an arrangement, it would be necessary to perform a check at each place where a return is about to be performed to ensure that it is safe to perform a return operation.
The present invention seeks to mitigate this and/or other problems.
The solution to these problems in a preferred embodiment of the invention is, at the point of deletion of the compiled code, to perform an examination of the virtual machine, looking for cases where a return address exists in the stacks that points to a position within the piece of compiled code to be deleted, and to re-arrange the thread""s stack contents to allow seamless continuation of execution of that thread without the compiled version of the code which is about to be deleted. The mechanism is preferably arranged such that the cost of the operation is borne at the time of deletion, with little or no extra cost at normal call/return time, since the relative frequency of the two situations is such that there are many more call/return operations than code deletion operations.
Accordingly, the invention in one aspect provides a method of examining memory in a computer system to allow a section of compiled code to be deleted, the method including:
examining a frame of a stack in the computer system;
identifying whether the frame contains a return address which is in the range of addresses of the section of compiled code; and
altering the contents of the frame when such a return address is identified.
By carrying out the above method, the problems associated with leaving a return address pointing into a section of compiled code to be deleted can be overcome.
In a closely related aspect of the present invention, there is provided a method of deleting compiled code in a computer system, including:
selecting a section of compiled code to be deleted;
examining a frame of a stack in the computer system;
identifying whether the frame contains a return address which is in the range of addresses of the section of compiled code;
altering the contents of the frame when such a return address is identified; and
deleting the section of compiled code.
Preferably any such return address is changed to the address of a piece of continuation code. The continuation code enables execution to continue after the return without the code to be deleted. Preferably, the continuation code is arranged to transfer control to an interpreter. The continuation code may be arranged so that subsequent instructions are interpreted, for example, until a section of emulated instructions is encountered for which there is a compiled version, or alternatively, to jump to a compiled version of the code to be deleted, if such a version exists. The use of a fallback interpreter for the execution of instructions subsequent to the return allows execution of the instructions of the deleted compiled code without the overhead of creating a new compiled version of the instructions.
If the frame contains such a return address, preferably, values in the frame are changed. Preferably, values in the frame are arranged to enable execution to continue without the code to be deleted. For example, temporary register information which is stored in the frame may be changed to take into account optimisations which were made when the code to be deleted was compiled. Such changes may be required, for example, where control is to be transferred to an interpreter for subsequent execution (see Agent""s reference no. 1 of this specification).
Preferably the alteration of the frame is carried out at the time of deletion. Thus, none of the links and return addresses of the frame will point into the compiled code after deletion, and time consuming checks during execution can be avoided.
Preferably, a plurality of frames in the stack are examined. For example, all frames in the stack may be examined, or else, each frame which may contain a return address pointing into the section of compiled code is examined.
In a preferred embodiment of the invention, the computer system operates a multi-threaded environment. Each thread has its own stack.
Preferably, the stacks of a plurality of threads in the computer system are examined. For example, the stacks of all threads in the computer system may be examined, or else, the stack of every thread to which the code to be deleted may have had access is examined.
In this way it can be ensured that no return addresses point into the section of compiled code to be deleted.
It may be known that some threads cannot have had access to the section of compiled code to be deleted. Execution time can be saved by not examining the stacks of such threads.
For the thread of the stack being examined, however, it will often be necessary to stop the thread while the examination is carried out. Alternatively, a return barrier may be inserted to restrict the thread to certain sections of the code (see Agent""s Reference No. 5 in this specification).
In another aspect of the present invention, there is provided a method of deleting compiled code in a computer system, including:
examining each frame of each stack of each thread in the system;
identifying whether a return address points to a portion of compiled code which is to be deleted; and
rearranging the contents of each stack containing the return address so as to enable that thread to continue execution without that portion of the compiled code which is to be deleted.
In a further aspect of the invention, there is provided a method of deleting a section of compiled code in a computer system, the method including, examining the memory of the computer system identifying a link to the section of compiled code and altering the link.
The link to the section of compiled code is preferably a return address in a frame. Thus, the return address identified when examining a frame is preferably a return address which is in the range of addresses of the section of compiled code to be deleted.
Alternatively, or in addition, the examination of the memory may identify a patch or other jump to the compiled code to be deleted. The link may be a direct or an indirect link to the compiled code to be deleted. For example, the link may be via a section of glue code to the section of compiled code.
Preferably, the computer system is configured as a virtual machine.
In a further aspect of the present invention, there is provided an apparatus for examining memory in a computer system to allow a section of compiled code to be deleted, including:
means for examining a frame of a stack in the computer system;
means for identifying whether the frame contains a return address which is in the range of addresses of the section of code to be deleted; and
means for altering the contents of the frame.
In another aspect of the present invention there is provided apparatus for deleting compiled code in a computer system, including:
means for selecting a section of compiled code to be deleted;
means for examining a frame of a stack in the computer system;
means for identifying whether the frame contains a return address which is in the range of addresses of the section of compiled code to be deleted;
means for altering the contents of the frame; and
means for deleting the section of compiled code.
The apparatus may further include means for executing subsequent instructions, and the means for arranging the contents of the frame may be adapted to change any such return address to the address of the means for executing subsequent instructions. Preferably, the apparatus further includes a fallback interpreter. The means for executing subsequent instructions may be arranged to interpret subsequent instructions until a section of emulated instructions is encountered for which there is a compiled version.
The means for arranging the contents of the frame may be adapted to alter values in the frame to enable execution to continue without the code to be deleted, if the frame contains such a return address.
In a preferred embodiment of the invention, a record is kept of the optimisations which have been carried out in compiling code so thatxe2x80x9cclean upxe2x80x9d information will be available as to what alterations are required to update the values to allow for the subsequent execution, for example, by the interpreter. For a computer system including the apparatus, preferably the system further includes a compiler system, the compiler system including a recorder for recordingxe2x80x9cclean upxe2x80x9d information as the code is compiled.
The means for examining a frame in the stack may be adapted to examine a plurality of frames in the stack. The means for examining a frame in the stack may be adapted to examine the stack of each of a plurality of threads in the computer system.
The invention also provides a virtual machine including the apparatus described above.
The invention further provides a computer system including the apparatus described above.
In another aspect, the invention provides a computer system including means for deleting compiled code, further including means for examining each frame of each stack of each thread in the system, means for identifying whether a return address points to a portion of compiled code which is to be deleted, and means for rearranging the contents of each stack containing the return address so as to enable that thread to continue execution without that portion of compiled code about to be deleted.
The invention further provides a computer-readable storage medium having a programme recorded thereon for carrying out a method as described above.
The features of any of the above aspects may be provided with any other aspect, in any appropriate combination. Apparatus features may be applied to the method aspects and vice versa.